|
In distributed computing, a shared snapshot object is a type of data structure, which is shared between several threads or processes. For many tasks, it is important to have a data structure, that can provide a consistent view of the state of the memory. In practice, it turns out that it is not possible to get such a consistent state of the memory by just accessing one shared register after another, since the values stored in individual registers can be changed at any time during this process. To solve this problem, snapshot objects store a vector of ''n'' components and provide the following two atomic operations: ''update(i,v)'' changes the value in the ''i''th component to ''v'', and ''scan()'' returns the values stored in all ''n'' components. Snapshot objects can be constructed using atomic single-writer multi-reader shared registers. In general, one distinguishes between single-writer multi-reader (swmr) snapshot objects and multi-writer multi-reader (mwmr) snapshot objects. In a swmr snapshot object, the number of components matches the number of processes and only one process ''Pi'' is allowed to write to the memory position ''i'' and all the other processes are allowed to read the memory. In contrast, in a mwmr snapshot object all processes are allowed to write to all positions of the memory and are allowed to read the memory as well. == General == A shared memory is partitioned into multiple parts. Each of these parts holds a single data value. In the single-writer multi-reader case each process ''Pi'' has a memory position ''i'' assigned and only this process is allowed to write to the memory position. However, every process is allowed to read any position in the memory. In the multi-writer multi-reader case, the restriction changes and any process is allowed to change any position of the memory. Any process ''Pi'' in an ''n''-process system is able to perform two operations on the snapshot object: ''scan()'' and ''update(i,v)''. The ''scan'' operation has no arguments and returns a consistent view of the memory. The ''update(i,v)'' operation updates the memory at the position ''i'' with the value ''v''. Both types of operations are considered to occur atomically between the call by the process and the return by the memory. More generally speaking, in the data vector each entry ''dk'' corresponds to the argument of the last linearized ''update'' operation, which updates part ''k'' of the memory. In order to get the full benefit of shared snapshot objects, in terms of simplifications for validations and constructions, there are two other restrictions added to the construction of snapshot objects. The first restriction is an architectural one, meaning that any snapshot object is constructed only with single-writer multi-reader registers as the basic element. This is possible for single-writer multi-reader snapshots. For multi-writer multi-reader snapshot objects it is possible to use multi-reader multi-writer registers, which can in turn be constructed from single-writer multi-reader registers.〔 In distributed computing the construction of a system is driven by the goal, that the whole system is making progress during the execution. Thus, the behaviour of a process should not bring the whole system to a halt (Lock-freedom). The stronger version of this is the property of wait-freedom, meaning that no process can prevent another process from terminating its operation. More generally, this means that every operation has to terminate after a finite number of steps regardless of the behaviour of other processes. A very basic snapshot algorithm guarantees system-wide progress, but is only lock-free. It is easy to extend this algorithm, so that it is wait-free. The algorithm by Afek et al., which is presented in the section Implementation has this property. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shared snapshot objects」の詳細全文を読む スポンサード リンク
|